#!/usr/bin/python

import math

def det(a11, a12, a21, a22):
    return a11*a22 - a12*a21

def line_intersection(l1, l2):
    (x1, y1), (x2, y2) = l1
    (x3, y3), (x4, y4) = l2

    C = det(x1 - x2, y1 - y2, x3 - x4, y3 - y4)
    if C == 0:
        return None
    a11 = det(x1, y1, x2, y2)
    a21 = det(x3, y3, x4, y4)
    A = det(a11, x1 - x2, a21, x3 - x4)
    B = det(a11, y1 - y2, a21, y3 - y4)
    return (A/C, B/C)

def orientation(a, b, c):
    # > 0 : clockwise, < 0 : counter-clockwise
    return ( b[0] - a[0] ) * ( c[1] - a[1] ) - ( c[0] - a[0] ) * ( b[1] - a[1] )

def quad_area((x1, y1), (x2, y2),
              (x3, y3), (x4, y4)):
    return 0.5 * math.fabs( x2*y1 - x4*y1 - x1*y2 + x3*y2 -
                            x2*y3 + x4*y3 + x1*y4 - x3*y4 )

def min_quad(P):
    """
    Finds the (maybe) minimum area quadrilateral that encloses a
    convex polygon.

    `P` is a list of the points that define the convex polygon, in
    counter-clockwise order.
    """
    n = len(P)
    def E(i):
        return (P[i], P[(i+1)%n])

    min_area = float('inf')
    min_quad = None

    for i in xrange(n):
        e1 = E(i)

        for j in xrange(i+1, n):
            e2 = E(j)
            v1 = line_intersection(e1, e2)
            if not v1: continue

            for k in xrange(j+1, n):
                e3 = E(k)
                v2 = line_intersection(e2, e3)
                if not v2: continue

                for l in xrange(k+1, n):
                    e4 = E(l)
                    v3 = line_intersection(e3, e4)
                    if not v3: continue
                    v4 = line_intersection(e4, e1)
                    if not v4: continue

                    if ((orientation(v3, v4, v1) <= 0) or
                        (orientation(v4, v1, v2) <= 0) or
                        (orientation(v1, v2, v3) <= 0) or
                        (orientation(v2, v3, v4) <= 0)):
                        continue

                    quad = [v1, v2, v3, v4]
                    area = quad_area(*quad)

                    # XXX: this first test below should not be needed
                    # but it's need currently, probably due to some
                    # bug or to a pathologycal case that we didn't
                    # consider :-(
                    if area > 200 and area < min_area:
                        min_area = area
                        min_quad = quad

    return min_quad
